package Z.dailyExercise._0223;

import java.util.Arrays;

public class _剑指Offer39数组中出现次数超过一半的数字 {

    //自解：排序 进行遍历
    //优化：众数一定是排序后的中间数
    public int majorityElement(int[] nums) {
        int len = nums.length;
        Arrays.sort(nums);

        int com=nums[0];
        int count = 1;
        for (int i=1;i<len;i++){
            if (nums[i] == com){
                count++;
            }else {
                com = nums[i];
                count=1;
            }

            if (count > len/2){
                return com;

            }
        }

        return com;

    }

    /**
     * 最优解：摩尔投票法--如果是众数 投票加一 其他减去1 最后的投票数必然》0
     * 并且 如果前面的票数已经抵消为0 后面剩余的部分仍然票数和》0
     *
     * 因此：借助此思想 假设第一个就是所求数 依次向后遍历 如果票数和为0 那么重新起头的数就是假设的新的所求数
     * 直到最后一轮假设的数字就是我们所求的
     */
    public int majorityElement1(int[] nums){
        int res = 0;
        int vote =0;
        for (int num:nums){
            if (vote==0){
                res = num;

            }
            if (num == res){
                vote++;
            }else {
                vote--;
            }
        }
        return res;
    }

}
